Due to the increase of operation frequency in recent LSI systems, signal propagation delays are required to achieve specifications with very high accuracy. In order to achieve the severe requirements, signal propagation delay is taken into account in the routing design of PCB (Printed Circuit Board). In the routing design of PCB, the controllability of wire length is often focused on since it enables us to control the routing delay. In this paper, we propose CAFE router which obtains routes of multiple nets with target wire lengths for single layer routing grid with obstacles. CAFE router extends the route of each net from a terminal to the other terminal greedily so that the wire length of the net approaches its target wire length. Experiments show that CAFE router obtains the routes of nets with small length error in short time.

In this paper, a novel high-performance heuristic algorithm, named relay-race algorithm (RRA), which was proposed to approach a global optimal solution by exploring similar local optimal solutions more efficiently within shorter runtime for NP-hard problem is investigated. RRA includes three basic parts: rough search, focusing search and relay. The rough search is designed to get over small hills on the solution space and to approach a local optimal solution as fast as possible. The focusing search is designed to reach the local optimal solution as close as possible. The relay is to escape from the local optimal solution in only one step and to maintain search continuity simultaneously. As one of typical applications, multi-objective placement problem in physical design optimization is solved by the proposed RRA. In experiments, it is confirmed that the computational performance is considerably improved. RRA achieves overall Pareto improvement of two conflicting objectives: power consumption and maximal delay. RRA has its potential applications to improve the existing search methods for more hard problems.

Multi-domain clock skew scheduling in general-synchronous framework is an effective technique to improve the performance of sequential circuits by using practical clock distribution network. Although the upper bound of performance of a circuit increases as the number of clock domains increases in multi-domain clock skew scheduling, the improvement of the performance becomes smaller while the cost of clock distribution network increases much. In this paper, a linear time algorithm that finds an optimum two-domain clock skew schedule in general-synchronous framework is proposed. Experimental results on ISCAS89 benchmark circuits and artificial data show that optimum circuits are efficiently obtained by our method in short time.

The most basic cross-talk minimization problem is to assign given n intervals to n parallel tracks where the cross-talk is defined between two intervals assigned to the adjacent tracks with the amount linear to parallel running length. This paper solves the problem for the case when any pair of intervals intersects and the objective is to minimize the sum of cross-talks. We begin the discussion with the fact that twice the sum of lengths of n/2 shortest intervals is a lower bound. Then an interval set that attains this lower bound is characterized with a simple assignment algorithm. Some additional considerations provide the minimum cross-talk for the other interval sets. The main procedure is to sort the intervals twice with respect to the length of left and right halves of intervals.